package com.wtgroup.demo.mianshi.算法.二叉树;

import com.wtgroup.demo.common.judge.Judger;
import com.wtgroup.demo.common.util.RandomUtil;
import com.wtgroup.demo.common.util.Sout;
import lombok.AllArgsConstructor;
import lombok.NoArgsConstructor;

import java.util.HashMap;
import java.util.HashSet;

/**
 * @author nisus
 * @version 0.1
 * @since 2023/5/4 21:33
 */
public class Q_最近公共祖先 {
    public static void main(String[] args) {
        Judger.of(() -> {
            Node tree = Util.generateRandomBST(RandomUtil.randomInt(0, 30), RandomUtil.randomInt());
            Node a = Util.pickRandomOne(tree);
            Node b = Util.pickRandomOne(tree);
            S1.Info info = new S1().doit(tree, a, b);
            Node res = S2.lowestAncestor1(tree, a, b);

            boolean ret = info.latestAncestor == res;
            if (!ret) {
                Sout.println(info.latestAncestor, res);
            }

            return ret;
        }).start().print();
    }

    static class S1 {

        static Info doit(Node head, Node a, Node b) {
            if (head == null) {
                return new Info(null, false, false);
            }

            Info leftInfo = doit(head.left, a, b);
            Info rightInfo = doit(head.right, a, b);

            Node latestAncestor = leftInfo.latestAncestor == null ?
                    (rightInfo.latestAncestor == null ? null : rightInfo.latestAncestor) : leftInfo.latestAncestor;
            boolean hasA = leftInfo.hasA || rightInfo.hasA || head == a;
            boolean hasB = leftInfo.hasB || rightInfo.hasB || head == b;

            if (latestAncestor == null) {
                // 左右子树都没有结果
                if (hasA && hasB) {
                    latestAncestor = head;
                }
            }

            return new Info(latestAncestor, hasA, hasB);
        }

        /*
        1. 左或右子树直接告诉我结果是.
        2. 左A,右B, 我是结果.
        3. 非2
         */
        @NoArgsConstructor
        @AllArgsConstructor
        static class Info {
            Node latestAncestor;
            boolean hasA;
            boolean hasB;
        }

    }

    static class S2 {
        public static Node lowestAncestor1(Node head, Node o1, Node o2) {
            if (head == null) {
                return null;
            }
            // key的父节点是value
            HashMap<Node, Node> parentMap = new HashMap<>();
            parentMap.put(head, null);
            fillParentMap(head, parentMap);
            HashSet<Node> o1Set = new HashSet<>();
            Node cur = o1;
            o1Set.add(cur);
            while (parentMap.get(cur) != null) {
                cur = parentMap.get(cur);
                o1Set.add(cur);
            }
            cur = o2;
            while (!o1Set.contains(cur)) {
                cur = parentMap.get(cur);
            }
            return cur;
        }

        public static void fillParentMap(Node head, HashMap<Node, Node> parentMap) {
            if (head.left != null) {
                parentMap.put(head.left, head);
                fillParentMap(head.left, parentMap);
            }
            if (head.right != null) {
                parentMap.put(head.right, head);
                fillParentMap(head.right, parentMap);
            }
        }
    }

}
